package com.lwl.Algorithmic_data_structure.class25单调栈;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description 给你一个数组，请你求出数组所有子数组最小值的累加和
 * @date 2023/6/26 11:26
 */
public class Code06GetSumOfSubMin {

    public static void main(String[] args) {
        /*
        2 6 6 7 7 1 2 4
        99
         */
        System.out.println(getSumOfSubMin(new int[]{2, 6, 6, 7, 7, 1, 2, 4}));
    }

    public static int getSumOfSubMin(int[] array) {
        int res = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        // 1. 找出每个元素在数组中比他小的边界（单调栈）
        for (int i = 0; i < array.length; i++) {
            while (!stack.isEmpty() && array[stack.peekLast()] >= array[i]) {
                // 2. 以每个元素作为最小值的子数组（边界为相等值时去掉重复值）
                // 似乎重复边界并不需要特殊处理
                Integer subMinIndex = stack.pollLast();
                int leftIndex = stack.isEmpty() ? 0 : stack.peekLast() + 1;
                int rightIndex = i - 1;
                int leftCount = subMinIndex - leftIndex + 1;
                int rightCount = rightIndex - subMinIndex + 1;
                int subMinSum = (leftCount * rightCount) * array[subMinIndex];
                res += subMinSum;
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            Integer subMinIndex = stack.pollLast();
            int leftIndex = stack.isEmpty() ? 0 : stack.peekLast() + 1;
            int rightIndex = array.length - 1;
            int leftCount = subMinIndex - leftIndex + 1;
            int rightCount = rightIndex - subMinIndex + 1;
            int subMinSum = (leftCount * rightCount) * array[subMinIndex];
            res += subMinSum;
        }
        return res;
    }

}
